#include "tree.h"
#include <stdlib.h>
#include <string.h>
/*
struct node_st {
  struct node_st *left, *right;
  char data[0];
};

typedef struct {
  struct node_st *root;
  int size;
} tree_t;

typedef int (*cmp_t)(const void *data, const void *key);
typedef void (*pri_t)(const void *data);
*/
// 初始化 树
int tree_init(tree_t **mytree, int size) {
  *mytree = malloc(sizeof(tree_t));
  if (*mytree == NULL) {
    return NULL;
  }
  (*mytree)->root = NULL;
  (*mytree)->size = size;
  return 0;
}

// 定义一个静态的接口用来创建节点
// 参数：数据，数据的大小
// 返回值：新节点的指针
static struct node_st *__new_node(const void *data, int size) {
  struct node_st *new = malloc(sizeof(struct node_st) + size);
  if (new == NULL) {
    return 0;
  }
  memcpy(new->data, data, size);
  new->left = new->right = NULL;
  return new;
}

// 定义一个静态的接口用来 插入节点
// 参数：根节点，新结点，比较函数指针
// 返回值：int
static int __insert_node(struct node_st **root, struct node_st *new_node,
                         cmp_t cmp) {
  // 先设定递归出口
  if ((*root) == NULL) {
    (*root) = new_node;
    return 0;
  }
  // 对根节点进行比较，比较之后进行递归
  if (cmp((*root)->data, new_node->data) >= 0) {
    return __insert_node(&(*root)->left, new_node, cmp);
  } else {
    return __insert_node(&(*root)->right, new_node, cmp);
  }
}

// 树的插入
int tree_insert(tree_t *mytree, const void *key, cmp_t cmp) {
  struct node_st *new = __new_node(key, mytree->size);
  if (new == NULL) {
    return -1;
  }
  return __insert_node(&mytree->root, new, cmp);
}
// 内部的查找接口
// 参数：二级指针的根节点，需要查找的数据，比较函数指针
// 返回值：节点的二级指针
static struct node_st **__find(struct node_st **root, void *key, cmp_t cmp) {
  if (*root == NULL) {
    return NULL;
  }
  int result = cmp((*root)->data, key);
  if (result == 0) {
    return root;
  } else if (result > 0) {
    return __find(&(*root)->left, key, cmp);
  } else {
    return __find(&(*root)->right, key, cmp);
  }
}

static struct node_st *__max_node(const struct node_st *root) {
  if (root == NULL) {
    return NULL;
  }
  if (root->right == NULL) {
    return root;
  }
  return __max_node(root);
}

static int __delete(struct node_st **root) {
  struct node_st *del, *r, *l;

  del = *root;
  r = del->right;
  l = del->left;
  del->right = del->left = NULL;
  free(del);
  del = NULL;
  if (l != NULL) {
    *root = l;
    __max_node(l)->right = r;
  } else {
    *root = r;
  }
  return 0;
}

int tree_delete(tree_t *mytree, const void *key, cmp_t cmp) {
  struct node_st **f = __find(&mytree->root, key, cmp);
  if (NULL == f) {
    return -1;
  }
  __delete(f);
  return 0;
}

void *tree_search(const tree_t *mytree, const void *key, cmp_t cmp) {
  struct node_st **f = __find(&mytree->root, key, cmp);
  if (NULL == f) {
    return NULL;
  }
  return (*f)->data;
}

static void __trval(const struct node_st *root, pri_t pri) {
  if (NULL == root) {
    return;
  }
  __trval(root->left, pri);
  pri(root->data);
  __trval(root->right, pri);
}

void tree_mid_traval(const tree_t *mytree, pri_t pri) {
  __trval(mytree->root, pri);
}

static void __destroy(struct node_st **root) {
  if (*root == NULL)
    return;
  __destroy(&(*root)->left);
  __destroy(&(*root)->right);
  free(*root);
  *root = NULL;
}

void tree_destroy(tree_t **mytree) {
  __destroy(&(*mytree)->root);
  free(*mytree);
  *mytree = NULL;
}

static int __node_cnt(const struct node_st *root) {
  if (NULL == root)
    return 0;
  return __node_cnt(root->left) + __node_cnt(root->right) + 1;
}

static struct node_st *__min_node(const struct node_st *root) {
  if (NULL == root)
    return NULL;
  if (root->left == NULL)
    return (struct node_st *)root;
  return __min_node(root->left);
}

static void __turn_left(struct node_st **root) {
  struct node_st *r, *cur;

  cur = *root;
  r = cur->right;

  *root = r;
  cur->right = NULL;
  __min_node(r)->left = cur;
}

static void __turn_right(struct node_st **root) {
  struct node_st *l, *cur;

  cur = *root;
  l = cur->left;

  *root = l;
  cur->left = NULL;
  __max_node(l)->right = cur;
}

static void __balance(struct node_st **root) {
  int n;

  if (*root == NULL)
    return;

  while (1) {
    n = __node_cnt((*root)->left) - __node_cnt((*root)->right);
    if (n >= 2) {
      __turn_right(root);
    } else if (n <= -2) {
      __turn_left(root);
    } else
      break;
  }
  __balance(&(*root)->left);
  __balance(&(*root)->right);
}

void tree_balance(tree_t *mytree) { __balance(&mytree->root); }
